public class 完全二叉树的节点个数 {

    //https://leetcode.cn/problems/count-complete-tree-nodes/
    //二分 ＋ 位运算 满二叉树
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        // 无参构造函数
        TreeNode() {}

        // 只带一个值的构造函数
        TreeNode(int val) {
            this.val = val;
        }

        // 带值、左子节点和右子节点的构造函数
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    //查找左节点的深度
    public int mostLeft(TreeNode root) {
        int level = 0;
        while(root != null){
            root = root.left;
            level++;
        }
        return level;
    }
    //存储二叉树的最大深度
    public static int h;

    public int countNodes(TreeNode root) {
        //为空直接返回0
        if(root == null){
            return 0;
        }
        h = mostLeft(root);

        return dfs(root,1);
    }
    public int dfs(TreeNode root,int level) {
        //如果层数与高度相同就返回
        if(level == h){
            return 1;
        }
        //当前层数的值 + 查找当前节点最大深度
        if(mostLeft(root.right) + level == h){
            //如果右子树的最左边扎到了, 说明左半边树是满二叉树, 所以直接加上, 继续递归右边的树
            return (1 << (h - level)) + dfs(root.right,level + 1);
        }else{
            //如果没有扎到, 说明右子树是满二叉树, 把右子树的节点算出, 然后递归左子树
            return (1 << (h - level - 1)) + dfs(root.left,level + 1);
        }
    }
}
